{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Successful Pairs of Spells and Potions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: successfulPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #咒语和药水的成功对数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数数组&nbsp;<code>spells</code> 和&nbsp;<code>potions</code>&nbsp;，长度分别为&nbsp;<code>n</code> 和&nbsp;<code>m</code>&nbsp;，其中&nbsp;<code>spells[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个咒语的能量强度，<code>potions[j]</code>&nbsp;表示第&nbsp;<code>j</code>&nbsp;瓶药水的能量强度。</p>\n",
    "\n",
    "<p>同时给你一个整数&nbsp;<code>success</code>&nbsp;。一个咒语和药水的能量强度 <strong>相乘</strong> 如果&nbsp;<strong>大于等于</strong>&nbsp;<code>success</code>&nbsp;，那么它们视为一对&nbsp;<strong>成功</strong>&nbsp;的组合。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>n</code>&nbsp;的整数数组<em>&nbsp;</em><code>pairs</code>，其中<em>&nbsp;</em><code>pairs[i]</code>&nbsp;是能跟第 <code>i</code>&nbsp;个咒语成功组合的 <b>药水</b>&nbsp;数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>spells = [5,1,3], potions = [1,2,3,4,5], success = 7\n",
    "<b>输出：</b>[4,0,3]\n",
    "<strong>解释：</strong>\n",
    "- 第 0 个咒语：5 * [1,2,3,4,5] = [5,<em><strong>10</strong></em>,<em><strong>15</strong></em>,<em><strong>20</strong></em>,<em><strong>25</strong></em>] 。总共 4 个成功组合。\n",
    "- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。\n",
    "- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,<em><strong>9</strong></em>,<em><strong>12</strong></em>,<em><strong>15</strong></em>] 。总共 3 个成功组合。\n",
    "所以返回 [4,0,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>spells = [3,1,2], potions = [8,5,8], success = 16\n",
    "<b>输出：</b>[2,0,2]\n",
    "<strong>解释：</strong>\n",
    "- 第 0 个咒语：3 * [8,5,8] = [<em><strong>24</strong></em>,15,<em><strong>24</strong></em>] 。总共 2 个成功组合。\n",
    "- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。\n",
    "- 第 2 个咒语：2 * [8,5,8] = [<em><strong>16</strong></em>,10,<em><strong>16</strong></em>] 。总共 2 个成功组合。\n",
    "所以返回 [2,0,2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == spells.length</code></li>\n",
    "\t<li><code>m == potions.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= spells[i], potions[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= success &lt;= 10<sup>10</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [successful-pairs-of-spells-and-potions](https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [successful-pairs-of-spells-and-potions](https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,3]\\n[1,2,3,4,5]\\n7', '[3,1,2]\\n[8,5,8]\\n16']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, q: List[int], a: List[int], b: int) -> List[int]:\n",
    "        a = sorted(a)\n",
    "        ans = []\n",
    "        for x in q:\n",
    "            y=len(a) - bisect_left(a, (b//x)+int(b%x>0))\n",
    "            ans.append(y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        potions.sort()\n",
    "        n , m = len(spells) , len(potions)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            l , r = 0 , m-1\n",
    "            if spells[i]*potions[l]>=success:\n",
    "                ans.append(m)\n",
    "            elif spells[i]*potions[r]<success:\n",
    "                ans.append(0)\n",
    "            else:\n",
    "                while l<=r:\n",
    "                    mid = int(l+(r-l)/2)\n",
    "                    if spells[i]*potions[mid]<success:\n",
    "                        l = mid + 1\n",
    "                    else:\n",
    "                        r = mid - 1 \n",
    "                ans.append(m-l)\n",
    "        return ans\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        rem = [-1] * 100001\n",
    "        res = []\n",
    "        potions.sort()\n",
    "        ll = len(potions)\n",
    "        for s in spells:\n",
    "            r = success / s\n",
    "            if rem[s] == -1:\n",
    "                rem[s] = ll - bisect.bisect_left(potions, r)\n",
    "            res.append(rem[s])    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        n,m=len(spells),len(potions)\n",
    "        potions.sort()\n",
    "        pair=[0]*n\n",
    "        minx=10**6\n",
    "        maxx=0\n",
    "        for i in range(n):\n",
    "            if spells[i]>=minx:\n",
    "                pair[i]=m\n",
    "                continue\n",
    "            if spells[i]<=maxx:\n",
    "                pair[i]=0\n",
    "                continue\n",
    "            left,right=0,m-1\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if spells[i]*potions[mid]>=success:\n",
    "                    right=mid-1\n",
    "                else :\n",
    "                    left=mid+1\n",
    "             \n",
    "            pair[i]=m-left\n",
    "            if pair[i]==m:\n",
    "                minx=min(minx,spells[i])\n",
    "            if pair[i]==0:\n",
    "                maxx=max(maxx,spells[i])\n",
    "        return pair\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路：排序后二分查找\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        n = len(spells)\n",
    "        m = len(potions)\n",
    "        potions = sorted(potions)\n",
    "        def bs(x):\n",
    "            left = 0\n",
    "            right = m-1\n",
    "            while left < right:\n",
    "                mid = (left+right) // 2\n",
    "                if potions[mid] < x:\n",
    "                    left = mid +1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "\n",
    "        res = [0] * n\n",
    "        for idx, i in enumerate(spells):\n",
    "            t = math.ceil(success / i)\n",
    "            if t <= potions[0]:\n",
    "                res[idx] = m\n",
    "            elif t > potions[-1]:\n",
    "                continue\n",
    "            else:\n",
    "                res[idx] = m-bs(t)\n",
    "\n",
    "            # print(t, bs(t))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        potions.sort()\n",
    "        n=len(spells)\n",
    "        res=[0]*n\n",
    "        m=len(potions)\n",
    "        for i in range(n):\n",
    "            if spells[i]*potions[m-1]<success:\n",
    "                res[i]=0\n",
    "                continue\n",
    "            if spells[i]*potions[0]>=success:\n",
    "                res[i]=m\n",
    "                continue\n",
    "            left,right=0,m-1\n",
    "            while (left+1)<right:\n",
    "                mid=(left+right)//2\n",
    "                if spells[i]*potions[mid]>=success:\n",
    "                    right=mid\n",
    "                elif spells[i]*potions[mid]<success:\n",
    "                    left=mid\n",
    "                else:\n",
    "                    \n",
    "                    break\n",
    "            mid=right\n",
    "            res[i]=(m-mid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        ans = []\n",
    "        potions.sort()\n",
    "        lp = len(potions)\n",
    "        for spell in spells:\n",
    "            l = 0\n",
    "            r = lp\n",
    "            i = (l + r) // 2\n",
    "            if spell * potions[lp - 1] < success:\n",
    "                ans.append(0)\n",
    "            elif spell * potions[0] >= success:\n",
    "                ans.append(lp)\n",
    "            elif spell * potions[lp - 1] == success:\n",
    "                ans.append(lp - potions.index(potions[lp - 1]))\n",
    "            else:\n",
    "                while not (spell * potions[i] < success and spell * potions[i + 1] >= success):\n",
    "                    while spell * potions[i] < success and (not (spell * potions[i] < success and spell * potions[i + 1] >= success)):\n",
    "                        l = i\n",
    "                        i = (l + r) // 2\n",
    "                    while spell * potions[i] >= success and (not (spell * potions[i] < success and spell * potions[i + 1] >= success)):\n",
    "                        r = i\n",
    "                        i = (l + r) // 2\n",
    "                ans.append(lp - i - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        pairs = [0] * len(spells)\n",
    "        a = [i for i in range(len(spells))]\n",
    "        a.sort(key = lambda x: spells[x])\n",
    "        potions.sort(reverse = True)\n",
    "        j = 0\n",
    "        for i in a:\n",
    "            b = spells[i]\n",
    "            while j < len(potions) and b*potions[j] >= success:\n",
    "                j += 1\n",
    "            pairs[i] = j\n",
    "        return pairs\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        potions = sorted(potions)\n",
    "        n = len(potions)\n",
    "        res = []\n",
    "        for s in spells:\n",
    "            if s * potions[0] >= success:\n",
    "                res.append(n)\n",
    "                continue\n",
    "            elif s*potions[-1] < success:\n",
    "                res.append(0)\n",
    "                continue\n",
    "            else:\n",
    "                left, right = 0, n-1\n",
    "                while left<right:\n",
    "                    mid = (left+right) // 2\n",
    "                    if s * potions[mid+1] >= success and s*potions[mid] < success:\n",
    "                        break\n",
    "                    elif s * potions[mid+1] < success:\n",
    "                        left = mid+1\n",
    "                    elif s*potions[mid] >= success:\n",
    "                        right = mid\n",
    "                res.append(n-mid-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        n = len(spells)\n",
    "        res = [0]*n\n",
    "        idx = [i for i in range(n)]\n",
    "        idx = sorted(idx, key=lambda x: spells[x]) # 按照诅咒升序排序\n",
    "        potions.sort(reverse=True)\n",
    "        j = 0\n",
    "        for i in idx:\n",
    "            while j<len(potions) and spells[i]*potions[j]>=success: \n",
    "                j+=1\n",
    "\n",
    "            res[i] = j\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: list[int], potions: list[int], success: int) -> list[int]:\n",
    "        potions.sort()\n",
    "        ans = []\n",
    "\n",
    "        n = len(potions)\n",
    "        for spell in spells:\n",
    "            to = bisect.bisect_left(potions, success/spell)\n",
    "            ans.append(n-to)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        ret = []\n",
    "        potions.sort()\n",
    "        n = len(potions)\n",
    "        for item in spells:\n",
    "            temp = bisect_left(potions, success, key=lambda x: x*item)\n",
    "            ret.append(n-temp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        potions = sorted(potions)\n",
    "        pairs = []\n",
    "        for spell in spells:\n",
    "            left, right = 0, len(potions)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                product = potions[mid] * spell\n",
    "                if product >= success:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            \n",
    "            pairs.append(len(potions) - left)\n",
    "        \n",
    "        return pairs\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def binary_search(self, arr,low,high,spell,success) -> int:\n",
    "        # print(f\"high = {high} , low = {low}\")\n",
    "        if high > low:\n",
    "            mid = (high + low) // 2\n",
    "            if mid == 0 and  arr[mid] * spell >= success or arr[mid] * spell >= success and arr[mid - 1] * spell < success:\n",
    "                return mid\n",
    "            elif arr[mid] * spell >= success and arr[mid - 1] * spell >= success:\n",
    "                return self.binary_search(arr,low,mid,spell,success)\n",
    "            elif arr[mid] * spell < success and arr[mid - 1] * spell < success:\n",
    "                return self.binary_search(arr,mid + 1,high,spell,success)\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        result_list = []\n",
    "        potions.sort()\n",
    "        for i in range(len(spells)):\n",
    "            result = 0\n",
    "            binary_result = self.binary_search(potions,0,len(potions),spells[i],success)\n",
    "            # print(f\"binary_result = {binary_result}\")\n",
    "            if binary_result > -1:\n",
    "                result = len(potions) - binary_result\n",
    "            \n",
    "            result_list.append(result)\n",
    "        \n",
    "        return result_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        n = len(spells)\n",
    "        m = len(potions)\n",
    "\n",
    "        pairs = [0 for _ in range(n)]\n",
    "        required = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            required[i] = ceil(success / spells[i])\n",
    "\n",
    "        potions.sort()\n",
    "        unique_potions = [potions[0]]\n",
    "        unique_potions_nums = [1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            if potions[i] == potions[i - 1]:\n",
    "                unique_potions_nums[-1] += 1\n",
    "            else:\n",
    "                unique_potions_nums.append(1)\n",
    "                unique_potions.append(potions[i])\n",
    "        \n",
    "        for i in range(len(unique_potions_nums)-2, -1, -1):\n",
    "            unique_potions_nums[i] += unique_potions_nums[i+1]\n",
    "            \n",
    "\n",
    "        def bs(nums, target):\n",
    "            nlen = len(nums)\n",
    "\n",
    "            left, right, mid = 0, nlen - 1, 0\n",
    "\n",
    "            result = -1\n",
    "\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] == target:\n",
    "                    return mid\n",
    "                elif nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "\n",
    "            return left\n",
    "\n",
    "        for i in range(n):\n",
    "            idx = bs(unique_potions, required[i])\n",
    "            if idx < 0:\n",
    "                pairs[i] = m\n",
    "            elif idx == len(unique_potions):\n",
    "                pairs[i] = 0\n",
    "            else:\n",
    "                pairs[i] = unique_potions_nums[idx]\n",
    "\n",
    "        return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "\t\t\n",
    "        def quicksort_first(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            pivot = arr[len(arr) // 2]\n",
    "            left = [x/success for x in arr if x < pivot]\n",
    "            middle = [x/success for x in arr if x == pivot]\n",
    "            right = [x/success for x in arr if x > pivot]\n",
    "            return quicksort(left) + middle + quicksort(right)\n",
    "\n",
    "        def quicksort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return arr\n",
    "            pivot = arr[len(arr) // 2]\n",
    "            left = [x for x in arr if x < pivot]\n",
    "            middle = [x for x in arr if x == pivot]\n",
    "            right = [x for x in arr if x > pivot]\n",
    "            return quicksort(left) + middle + quicksort(right)\n",
    "            \n",
    "        result_list = []\n",
    "        potions = quicksort(potions)\n",
    "        for spell in spells:\n",
    "            success_target = success/spell\n",
    "            low_p = 0\n",
    "            high_p = len(potions) - 1\n",
    "            middle_p = 0\n",
    "            if potions[middle_p] >= success_target:\n",
    "                result_list.append(len(potions))\n",
    "                continue\n",
    "            while low_p < high_p:\n",
    "                middle_p = (low_p + high_p) // 2\n",
    "                if potions[middle_p] < success_target:\n",
    "                    if potions[middle_p+1] >= success_target:\n",
    "                        break\n",
    "                    low_p = middle_p\n",
    "                else:\n",
    "                    if potions[middle_p-1] < success_target:\n",
    "                        middle_p -= 1\n",
    "                        break\n",
    "                    high_p = middle_p\n",
    "                if middle_p + 1 == high_p:\n",
    "                    middle_p += 1\n",
    "                    break\n",
    "            result_list.append(len(potions) - middle_p - 1)\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        mem = []\n",
    "        for p in potions:\n",
    "            mem.append((p + success - 1) // p)\n",
    "        \n",
    "        # tle 突然发现可以二分\n",
    "        # ans = []\n",
    "        # for s in spells:\n",
    "        #     ans.append(sum([s >= x for x in mem]))\n",
    "        # return ans\n",
    "\n",
    "        # 左侧都可以\n",
    "        mem.sort()\n",
    "\n",
    "        def binary_search(x):\n",
    "            left, right = 0, len(mem) - 1\n",
    "            res = -1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if mem[mid] <= x:\n",
    "                    res = mid\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return res + 1\n",
    "\n",
    "        ans = []\n",
    "        for s in spells:\n",
    "            ans.append(binary_search(s))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findNumberOfElementsBelow(self, arr: List[int], target: int) -> int:\n",
    "        \"\"\"\n",
    "        This function should return the number of elements in arr (sorted) that is less than or equal to target using binary search. It should run in O(logN) time.\n",
    "        \"\"\"\n",
    "        if not arr:\n",
    "            return 0\n",
    "        left, right = 0, len(arr) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if arr[mid] <= target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left \n",
    "\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        16 // [8, 5, 8] -> get the upper floor \n",
    "        [2, 4, 2] -> how strong the spell needs to yield success with this potion \n",
    "        [2, 2, 4] -> after sorted \n",
    "        for spell = 3, use binary search to find 2 spells [2, 2]\n",
    "        for spell = 1, use binary search to find 0 spell \n",
    "        for spell = 2, use binary search to find 2 spells \n",
    "        return [2, 0, 2]\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        # get the minimal spell strength array \n",
    "        minimal_spell_strength = [math.ceil(success / potion) for potion in potions]\n",
    "        # sort \n",
    "        minimal_spell_strength.sort()\n",
    "        # itereate through spells to perform binary search to count the number of elements <= spell \n",
    "        for spell in spells:\n",
    "            ret.append(self.findNumberOfElementsBelow(minimal_spell_strength, spell))\n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        # potions = sorted(potions)\n",
    "        # res = []\n",
    "        # length = len(potions)\n",
    "        # for spell in spells:\n",
    "        #     val = success//spell\n",
    "        #     if spell * val < success:\n",
    "        #         val += 1\n",
    "        #     index = bisect.bisect_left(potions,val)\n",
    "        #     res.append(length-index)\n",
    "        # return res\n",
    "        idx = [(index,spells[index]) for index in range(len(spells))]\n",
    "        idx = sorted(idx,key=lambda x :x[1])\n",
    "        potions = sorted(potions)\n",
    "        potions.reverse()\n",
    "        res = [0]*len(spells)\n",
    "        j = 0\n",
    "        for index,val in idx:\n",
    "            while j < len(potions) and val * potions[j] >= success:\n",
    "                j += 1\n",
    "            res[index] = j\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        \n",
    "        potions.sort()\n",
    "        potions=[success / i  for i in potions]\n",
    "        potions = potions[::-1] \n",
    "        print(potions)\n",
    "        ans=[]\n",
    "        for i in spells:\n",
    "            print(bisect_right(potions,i))\n",
    "            ans.append(bisect_right(potions,i))\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        copied = spells[:]\n",
    "        copied.sort()\n",
    "\n",
    "        potions.sort(reverse=True)\n",
    "        p = 0\n",
    "        m = {}\n",
    "        for a in copied:\n",
    "            while p < len(potions):\n",
    "                b = potions[p]\n",
    "                if a * b >= success:\n",
    "                    p += 1\n",
    "                else:\n",
    "                    break\n",
    "            if p == len(potions) and potions[-1] * a < success:\n",
    "                continue\n",
    "            m[a] = p\n",
    "        \n",
    "        ret = [m.get(n, 0) for n in spells]\n",
    "        return ret "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        n = len(spells)\n",
    "        m = len(potions)\n",
    "        ret = [0] * n\n",
    "        dic = {}\n",
    "        #对potions进行排序\n",
    "        potions.sort()\n",
    "        #二分查找，查找第一个spell * nums[i] 大于等于target的位置\n",
    "        def search(nums,spell,target):\n",
    "            ans = len(nums)\n",
    "            left = 0\n",
    "            right = len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                temp = nums[mid] * spell\n",
    "                if temp >= target:\n",
    "                    ans = mid\n",
    "                    right = mid - 1\n",
    "                else:left = mid + 1\n",
    "            return ans\n",
    "        for i in range(n):\n",
    "            if spells[i] in dic:\n",
    "                ret[i] = dic[spells[i]]\n",
    "                continue\n",
    "            ret[i] = m - search(potions,spells[i],success)\n",
    "            dic[spells[i]] = ret[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        spells1=sorted(spells)\n",
    "        potions.sort()\n",
    "        res=defaultdict(int)\n",
    "        #pairs=[]\n",
    "        m=len(spells)\n",
    "        n=len(potions)\n",
    "\n",
    "        for i in range(m):\n",
    "            if spells1[i]>=success:\n",
    "                for j in range(i,m):\n",
    "                    res[spells1[j]]=n\n",
    "                break\n",
    "            else:\n",
    "                k=success/spells1[i]\n",
    "            index=bisect.bisect_left(potions,k)\n",
    "            res[spells1[i]]=n-index\n",
    "\n",
    "        pairs=[res[v] for v in spells]\n",
    "\n",
    "        return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#[1  2   3   4    5]  spell = 5  sucess = 7\n",
    "# s      m        e\n",
    "# s  m   e      \n",
    "# sm e\n",
    "# e  s\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        # spells.sort()\n",
    "        potions.sort()\n",
    "        start, end = 0, len(potions)-1\n",
    "        result = {}\n",
    "\n",
    "        for spell in sorted(spells):\n",
    "            if spell in result:\n",
    "                continue\n",
    "            start = 0\n",
    "            while start <= end:\n",
    "                mid = (start+end) // 2\n",
    "                if spell * potions[mid] >= success:\n",
    "                    end = mid-1\n",
    "                else:\n",
    "                    start = mid+1\n",
    "            assert start == end+1\n",
    "            assert end==len(potions)-1 or spell * potions[end+1] >= success\n",
    "            assert end<0 or spell * potions[end] < success\n",
    "            result[spell] = len(potions) -1 - end\n",
    "        \n",
    "        return [result[s] for s in spells]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int],\n",
    "                        success: int) -> List[int]:\n",
    "        potions.sort()\n",
    "        pStrengths = [[potions[0], 0]]\n",
    "        for potion in potions:\n",
    "            if potion == pStrengths[-1][0]:\n",
    "                pStrengths[-1][1] += 1\n",
    "            else:\n",
    "                pStrengths.append([potion, 1])\n",
    "        for i in range(len(pStrengths) - 2, -1, -1):\n",
    "            pStrengths[i][1] += pStrengths[i + 1][1]\n",
    "        print(pStrengths)\n",
    "\n",
    "\n",
    "        ans = [0] * len(spells)\n",
    "        for i, spell in enumerate(spells):\n",
    "            cnt = bisect_left(pStrengths, (success + spell - 1) // spell, key=lambda x: x[0])\n",
    "            ans[i] = pStrengths[cnt][1] if cnt < len(pStrengths) else 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:\n",
    "        spells_len, potions_len = len(spells), len(potions)\n",
    "        ans = [potions_len for _ in range(spells_len)] \n",
    "        t = []\n",
    "        for i in range(spells_len):\n",
    "            t.append([i, spells[i]])\n",
    "        t.sort(key=lambda x:x[1])\n",
    "        potions.sort()\n",
    "        \n",
    "        for idx,value in t:\n",
    "            if value * potions[0] >= success:\n",
    "                break \n",
    "            l, r = 0, len(potions) - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if value * potions[mid] < success:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans[idx] -= l\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
